--[[
    快速排序
    可做优化的点的
        1. 选取划分值，如果选到最大或最小值会增加排序次数，（可以取1，m, end, 中间的值, 对于数据量比较大的还是不错的
        2. 抽出划分值，让需要调换的值直接付值而不用交换, 最后把划分值付于nodes[left]位置

    node = {
        id 作为大小比较值
    }
--]]


require("dump")

local table_insert = table.insert
local table_remove = table.remove

local QSort = {}

function QSort.new(...)
    local instance = setmetatable({}, {__index=QSort})
    instance:ctor(...)
    return instance
end

function QSort:ctor()
    self.nodes = {} --用于存放数据
end

--
function QSort:push(node)
    table_insert(self.nodes, node)
    return
end

--优先取id值大的node
function QSort:pop()
    if not self.nodes or not self.nodes[1] then
        return
    end
    local value = self.nodes[1]
    table_remove(self.nodes, 1)
    return value
end

function QSort:getTop()
    return self.nodes[1]
end

function QSort:getNodes()
    return self.nodes
end

function QSort:print()
    for i = 1, #self.nodes do
        print(i, self.nodes[i].id)
    end
end

function QSort:size()
    return #self.nodes
end

function QSort:sort(left, right)
    if not left and not right then
        left = self:getPatitionKey()
        right = self:size()
    end
    if left > right then
        return
    end
    local pivot = self:partition(left, right, nodes) --分段
    self:sort(1,pivot-1) --对左边子集排序
    self:sort(pivot+1, right) --对右边子集排序
end

--划分函数
function QSort:partition(left, right, nodes)
    if not nodes then
        nodes = self.nodes
    end
    local key_node = nodes[left] --分割点
    local key_id = key_node.id
    while left < right do --这一轮要求左边的数<key_id, 右边的数大于key_id
        while left < right and nodes[right].id >= key_id do --在右边找到一个小于key_id的数
            right = right - 1
        end
        nodes[left] = nodes[right] --left位置的数已经保存到临时变量，可以直接放置比key_id小的数

        while left < right and nodes[left].id <= key_id do --左边找到一个比key_id大的数
            left = left + 1
        end
        --因为right位置的数已移走，位置空着
        nodes[right] = nodes[left]
    end
    nodes[left] = key_node --把分割点放到空位置上
    return left
end

--取一个分割点
function QSort:getPatitionKey(nodes)
    if not nodes then
        nodes = self.nodes
    end
    local left = 1
    local right = #nodes
    local mid = math.floor((left+right)/2)
    local tb = {left, right, mid}
    local average = math.floor((nodes[left].id + nodes[right].id + nodes[mid].id)/3)
    local key = left
    local min = math.abs(nodes[left].id - average)
    for k, v in pairs(tb) do
        local value = math.abs(nodes[v].id - average)
        if min > value then
            min = value
            key = v
        end
    end
    return key
end

------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "qsort.lua" then
    local qsort = QSort.new()
    qsort:push({id=2})
    qsort:push({id=12})
    qsort:push({id=1})
    qsort:push({id=8})
    qsort:push({id=6})
    qsort:push({id=5})
    qsort:push({id=6})
    qsort:push({id=16})
    qsort:push({id=26})
    qsort:print()
    print("_______")
    qsort:sort()
    qsort:print()
    print("_______")

    print("____min:", tostring(qsort:pop()))
    --print("____min:", tostring(qsort:pop()))
end

return QSort